\documentclass[12pt,titlepage]{article}
\usepackage[spanish]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}

\usepackage{color}
\usepackage{graphicx} % para insertar imagenes
\usepackage{verbatim}

\newcommand{\VSP}{\vspace*{3em}}
\newcommand{\Pa}{\vspace{5mm}}

\title{{\sc\normalsize Sistemas Operativos}\\{\bf Trabajo Práctico Nº1\\ \Pa} {\texttt Grupo 12}}
\author{\begin{tabular}{lcr}
Carla Livorno & 424/08 & carlalivorno@hotmail.com\\Thomas Fischer & 489/08 & tfischer@dc.uba.ar
\end{tabular}}
\date{\VSP \normalsize{Septiembre 2010}}
%\date{}
\begin{document}
\begin{titlepage}
\maketitle
\end{titlepage}
\tableofcontents
\newpage

\begin{section}{Ejercicio 1}
	Este ejercicio consistió en armar un conjunto de tareas que arrojaran
	los diagramas de Gantt presentados en el enunciado con las políticas
	de scheduling correspondientes. \\

	Primero mirando la escala en lós gráficos definimos
	el tiempo de ejecución de cada proceso. \\

	Con el diagrama de scheduling \texttt{FCFS} comenzamos a definir
	un órden de llegada para las tareas.
	Por ejemplo nos dimos cuenta que \texttt{P1} debía llegar exactamente
	en el instante $5$ ya que apenas llega el primer proceso el scheduler
	lo manda a procesar. \\
	
	Luego con el diagrama de scheduling \texttt{SJF} vimos que \texttt{P2}
	también debía llegar en el instante $5$ ya que si llegaba más tarde
	también se hubiese encolado \texttt{P1} en primer lugar por ser
	el único proceso a ejecutar.

	Luego, también analizando el segundo diagrama, decidimos que \texttt{P3}
	debía llegar antes que \texttt{P2} terminase su ejecución,
	sino el scheduler hubiese elegido \texttt{P1} como siguiente
	proceso a ejecutar por la misma razón que antes. \\

	Los resultados finales fueron los siguientes: \\

	\begin{tabular}{ccc}
		\texttt{P1} & $10$ & $5$ \\
		\hline
		\texttt{P2} & $5$ & $5$ \\
		\hline
		\texttt{P3} & $5$ & $6$ \\
	\end{tabular}
	
\end{section}

\begin{section}{Ejercicio 2}
	En este ejercicio tuvimos que modificar los códigos de los schedulers
	\texttt{FCFS} y \texttt{SJF} para que calculasen el \textit{waiting time}
	de cada proceso. \\

	Fue bastante fácil de implementar, ya que estás políticas de scheduling
	no hacen desalojo. Por lo tanto cuando un proceso comienza a ejecutarse
	no se corta hasta terminar, por lo cuál no se suma más tiempo de espera al mismo.
	Entonces el tiempo de espera resulta ser el que espero el proceso
	desde que llegó a la cola (\texttt{rtime}) hasta que comenzó a ejecutarse. \\

	Luego para implementarlo en cada algoritmo solo tuvimos que encontrar
	los lugares donde un proceso nuevo se empezaba a ejecutar
	y hacer ahí la cuenta antes mencionada.
\end{section}

\begin{section}{Ejercicio 3}
	Para calcular el tiempo promedio de espera en una carga del scheduler,
	simplemente tomamos el promedio del tiempo de espera
	de todos los procesos luego de su ejecución.
\end{section}

\begin{section}{Ejercicio 4}
	El objetivo de este ejercicio es comparar el comportamiento de los
	algoritmos FCFS y SJF mediante la simulación de los conjuntos
	de tareas definidos por la cátedra. \\

	A continuación mostramos el tiempo de espera promedio de una tarea
	con distintos \textit{tasksets} para estos algoritmos. \\

	\begin{tabular}{|c|c|c|}
		\hline
			& \texttt{FCFS} & \texttt{SJF} \\
		\hline
		ts1 & 87 & 87 \\
		ts2 & 192 & 122 \\
		ts3 & 127 & 105 \\
		ts4 & 77 & 58 \\
		ts5 & 144 & 56 \\
		ts6 & 176 & 57 \\
		\hline
	\end{tabular} \VSP

	Luego de simular cada $taskset$ observamos que el tiempo promedio
	de espera mejora con el algoritmo SJF.
	Sabemos que SJF es óptimo si se conoce
	todas las tareas desde un principio como pasa con el $taskset$ $ts3$.
	Si esto no sucede, mientras más juntas lleguen las tareas,
	de manera que al iniciar una nueva el scheduler pueda tomar
	una decisión más adecuada, mejor funcionará el scheduler. \\

	Los primeros cuatro $taskset$ tienen las mismas tareas
	($ocho$ tareas con tiempos de ejecución de $10$ a $80$)
	pero difieren los tiempos de llegada de cada tarea.

	En $ts1$ las tareas llegan de forma creciente con respecto
	al tiempo de ejecución por lo que FCFS ejecuta siempre una tarea
	más corta antes que otra que es más larga y por lo tanto se comporta
	igual que el algoritmo SJF.
	Por eso se da que ambos algoritmos tienen el mismo tiempo de
	espera promedio. \\

	En $ts2$ las tareas llegan de forma decreciente con respecto
	al tiempo de ejecución por lo que FCFS ejecuta siempre una
	tarea más larga antes que otra más corta.
	Al contrario de esto SJF ejecuta la tarea más larga primero porque
	no hay otra para ejecutar en ese momento pero al terminar
	dicha tarea ya estan todas las demas en la cola de listos
	por lo que empieza a ejecutar desde la tarea más corta hacia
	la más larga.
	A esto se debe que mejora mucho el tiempo de espera promedio. \\

	Por otro lado, en $ts6$ hay una tarea muy larga en comparación
	al resto que FCFS ejecuta en 4to lugar, lo que retrasa al resto
	de las tareas.
	En cambio SJF consigue el tiempo de espera óptimo ya que llegan
	todas en el instante cero y logra asi una notable diferencia. \\

	Claramente estos algoritmos no son para nada buenos en los casos
	en que se trata simular un servidor (como \texttt{ts5} y \texttt{ts6})
	ya que se trata de políticas sin desalojo y hay procesos que corren
	constantemente (un demonio servidor por ejemplo) y que bloquearían
	la cola de tareas para siempre. \\

	Además el algoritmo \texttt{SJF} que teóricamente parece ser óptimo
	en muchos sentidos, en la práctica resulta difícil de utilizar
	ya que estimar el tiempo necesario de ejecución de un proceso
	puede ser muy difícil o incluso imposible.
	
\end{section}

\begin{section}{Ejercicio 5}
	En este ejercicio tuvimos que implementar la simulación
	del algoritmo de $Round-Robin$ que es análoga a $FCFS$
	con la diferencia que la primera de estas politicas desaloja a
	las tareas, si no terminaron, una vez que se cumple un tiempo determinado
	($quantum$) pasado como parámetro al algoritmo, y las encola de
	nuevo atras de todo. \\

	Para analizar el comportamiento del algoritmo simulamos la ejecución
	de cada $taskset$ variando el $quantum$ y tomando en cuenta
	los tiempos de espera promedio para una tarea en cada uno.

	A continuación se presentan los resultados obtenidos de este experimento.\\

	\begin{tabular}{|c|c|c|c|c|c|}
		\hline
			& \texttt{q=1} & \texttt{q=10}  & \texttt{q=50} & \texttt{q=100} & \texttt{q=150}\\
		\hline
		ts1 & 672 & 193 & 115 & 94 & 94\\
		ts2 & 718 & 255 & 243 & 199 & 199\\
		ts3 & 710 & 230 & 155 & 134 & 134\\
		ts4 & 624 & 150 & 105 & 84 & 84\\
		ts5 & 408 & 131 & 116 & 140 & 151\\
		ts6 & 399 & 132 & 139 & 168 & 185\\
		\hline
	\end{tabular} \VSP

	Para esto empezamos probando con un $quantum$ igual a una unidad
	de tiempo con el que observamos que el tiempo de espera promedio
	fue muy elevado para todos los conjuntos de tareas, es decir,
	se hacen irrelevantes las caracteristicas de estos conjuntos
	(duración de la tarea y tiempo de llegada a la cola de listos)
	ya que lo que produce ese tiempo de espera promedio es el hecho
	de que el sistema esta más tiempo haciendo cambios de contextos
	que ejecutando las tareas (el cambio de contexto ya
	tarda dos unidades de tiempo que es mayor al $quantum$ usado). \\

	Luego probamos con un $quantum$ igual a diez unidades de tiempo
	con el que vimos que mejoraba notablemente el tiempo de espera
	promedio en comparación al anterior lo que es razonable
	ya que el tiempo perdido en cambios de contexto empieza a ser
	menos relevante en el tiempo total. \\

	Pensando que un $quantum$ de diez unidades de tiempo podría
	todavia no resultar un número equilibrado entre el tiempo
	de ejecución y el tiempo de cambio de contexto decidimos probar
	tambien con un $quantum$ igual a 50 unidades de tiempo.
	Al simular los $taskset$ con este $quantum$ notamos que seguia
	mejorando el tiempo de espera promedio (salvo en el ts6 pero con
	una pequeña diferencia) lo que nos hizo pensar que ya podriamos
	estar en un valor adecuado o muy cercano al óptimo para estos
	conjuntos en particular.

	Finalmente probamos con un $quantum$ igual a cien unidades de tiempo
	con el objetivo de corroborar que $RR$ se comporta como $FCFS$
	salvo por los cambios de contexto entre las tareas (que en $FCFS$
	no esta simulado). Elegimos cien porque en los primeros $taskset$
	la tarea más larga dura 80 unidades de tiempo (con un quantum de 80
	hubiese alcanzado) y en los otros dos conjuntos sólo una tarea
	excede ese tiempo.
	Para convencernos de que por más que aumentemos el quantum el tiempo
	de espera promedio para los primeros conjuntos no cambia
	los simulamos con un $quantum$ de $150$, que es recien
	el valor donde los dos últimos conjuntos de tarea se comportan
	como $FCFS$. \\

	Algo a tener en cuenta, es que la performance parece disminuír
	notablemente con respecto a los algoritmos sin desalojo como
	\texttt{FCFS} y \texttt{SJF} en algunos casos, en particular
	en aquellos donde hay tareas grandes corriendo constantemente,
	que son las más parecidos a sistemas orientados a servidores o de
	propósito general. \\

	Una gran ventaja de este (y otros) algoritmos con desalojo,
	es que a diferencia de los otros sin desalojo, el usuario del
	sistema va a tener una sensación de simultaneidad al ejecutar
	varios programas a la vez. Además, el sistema no necesariamente va
	a colgarse si un programa nunca termina. \\
	
\end{section}

\begin{section}{Ejercicio 6}

	El ejercicio consistió en implementar un scheduler con una política
	\texttt{Multilevel Feedback Queue (MFQ)} de 3 colas con distintos
	niveles de prioridad, con quantums distintos de $5$ (para la mayor
	prioridad), $15$ y $45$ (para la menor prioridad).

	A continuación presentamos los resultados de tiempo promedio
	de espera por proceso obtenidos, en comparación con los algoritmos
	presentados anteriormente. \\

	\begin{tabular}{|c|c|c|c|c|c|}
		\hline
			& \texttt{FCFS} & \texttt{SJF} & \texttt{RR(q=50)} & \texttt{RR(q=100)} & \texttt{MFQ} \\
		\hline
		ts1	& 87	& 87	& 115	& 94	& 171 \\
		ts2	& 192	& 122	& 243	& 199	& 259 \\
		ts3	& 127	& 105	& 155	& 134	& 217 \\
		ts4	& 77	& 58	& 105	& 84	& 148 \\
		ts5	& 144	& 56	& 116	& 140	& 138 \\
		ts6	& 176	& 57	& 139	& 168	& 145 \\
		\hline
	\end{tabular} \VSP

	Vemos que de nuevo hay una gran diferencia con los algoritmos sin desalojo,
	como era de esperarse. \\
	
	También vemos que comparado con \texttt{RR}, en los tasks $1-4$,
	cuyas tareas son bastante parecidas, parece poco conveniente
	utilizar \texttt{MFQ}, pero en las tareas $5$ y $6$, que tienen pocas
	tareas muy largas y muchas otras chicas (podemos hablar por ejemplo
	de servidores y sistemas multipropósito) este algoritmo parece ser
	notablemente mejor.

\end{section}

\begin{section}{Ejercicio 7}
	Este ejercicio consistió en agregar al scheduler \texttt{MFQ}
	la funcionalidad de simular eventos aleatorios de entrada/salida
	de las tareas que se ejecutaban. \\

	Para esto cada vez que una tarea entraba en ejecución, un valor
	de verdad aleatorio decidía si en ese quantum la tarea tenía que
	realizar operaciones de entrada salida o no, ambos casos igualmente
	probables.
	En caso afirmativo, otro valor aleatorio decide a los cuántos ticks
	de ejecución en ese quantum la tarea inicia dichas operaciones.
	Y al comenzarlas, un nuevo valor aleatorio decide cuánto tiempo
	va a tomar (valor entre $1$ y $5$).

	Para implementar esto, tuvimos que agregar a la información
	del proceso (clase \texttt{Task}), el tiempo faltante para terminar
	una operación de entrada/salida (de haberla).

	Este scheduler esta implementado en la clase \texttt{MFQ2} para
	lo cuál modificamos un poco el simulador para que lo soporte
	como parámetro.
\end{section}

\end{document}
